/*
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/out-of-boundary-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
protected:
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn)
    {
        const int mod = 1e9 + 7;
        vector<vector<int>> d{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<vector<int>> dp(m, vector<int>(n));
        for (int i = 1; i <= maxMove; i++)
        {
            vector<vector<int>> tmp(m, vector<int>(n));
            for (int j = 0; j < m; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    for (int l = 0; l < 4; l++)
                    {
                        int dx = j + d[l][0];
                        int dy = k + d[l][1];
                        if (dx < 0 || dx >= m || dy < 0 || dy >= n)
                            tmp[j][k]++;
                        else
                            tmp[j][k] = (tmp[j][k] + dp[dx][dy]) % mod;
                    }
                }
            }
            dp = tmp;
        }
        return dp[startRow][startColumn];
    }
};